package bite;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:【最长上升子序列】广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。 例如队伍的身高
 * 数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。
 * User:yxd
 * Date:2022-06-20
 * Time:21:16
 */
public class Day40_2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int[] arr = new int[n];
            for(int i = 0;i < n;i ++){
                arr[i] = input.nextInt();
            }
            //状态定义:F(i)表示当前元素结尾的最长子序列
            //状态转移方程:比较当前元素和前面所有元素的大小,如果有前面的元素小于当前元素就可以更新当前最长子序列为较小元素和当前元素的较大最长子序列F(i) = max(f(i),F(j) + 1))
            //赋初值F(0) = 1
            int[] dp = new int[n];
            //记录最长的序列
            int count = 1;
            dp[0] = 1;
            for(int i = 1;i < n;i ++){
                //每个最长子序列都包含这个元素本身
                dp[i] = 1;
                //比较和前面所有元素的大小,看是否需要更新
                for(int j = 0;j < i;j ++){
                    if(arr[j] < arr[i]){
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                }
                count = Math.max(count,dp[i]);
            }
            System.out.println(count);
        }
    }
}
